package t_127

import "math"

/**

 */
//func ladderLength(beginWord string, endWord string, wordList []string) int {
//	return dfs(beginWord, endWord, wordList)
//}

//beginWord := "hit"
//endWord := "cog"
//wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
/**
递归求取满足条件最小次数
*/
//func dfs(beginWord string, endWord string, wordList []string) int {
//	// getMin
//	mimic := getMimic(beginWord, wordList)
//	return 0
//}
//
//func getMimic(word string, list []string) interface{} {
//	for i := 0; i < len(list); i++ {
//		return isMimic()
//	}
//
//	return nil
//}

func ladderLength(beginWord string, endWord string, wordList []string) int {
	// map
	wordId := map[string]int{}
	var graph [][]int

	// method
	addWord := func(word string) int {
		id, has := wordId[word]
		if !has {
			id = len(wordId)
			wordId[word] = id
			graph = append(graph, []int{})
		}
		return id
	}

	// method
	addEdge := func(word string) int {
		id1 := addWord(word)
		s := []byte(word)
		for i, b := range s {
			s[i] = '*'
			id2 := addWord(string(s))
			graph[id1] = append(graph[id1], id2)
			graph[id2] = append(graph[id2], id1)
			s[i] = b
		}
		return id1
	}

	for _, word := range wordList {
		addEdge(word)
	}

	beginId := addEdge(beginWord)
	endId, has := wordId[endWord]

	if !has {
		return 0
	}

	const inf int = math.MaxInt64
	dist := make([]int, len(wordId))
	for i := range dist {
		dist[i] = inf
	}
	dist[beginId] = 0
	queue := []int{beginId}

	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		if v == endId {
			return dist[endId]/2 + 1
		}
		for _, w := range graph[v] {
			if dist[w] == inf {
				dist[w] = dist[v] + 1
				queue = append(queue, w)
			}
		}
	}

	return 0
}
